package com.vincent.algorithms.stackandlist;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

/**
 *
 * 双向链表的应用
 * 生成窗口最大值数组
 * 即给出数组 和 窗口大小  返回最大值数组
 * 例如[3,5,2,7,3,6,1]  返回[5,7,7,7,6]
 *
 * Created by yangwenchang on 2017/8/28.
 */
public class MaxWindow {

    public static void getMaxWindow(int[] arr,int w){

        int[] maxWindow =new int[arr.length-w+1];
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        linkedList.get(5);
        for (int i=0;i<arr.length;i++){

            if (linkedList.isEmpty()){
                linkedList.add(i);
            }else{
                int max = linkedList.getFirst();
                // 是否需要选出
                if (i<(w-1)) {
                    while (!linkedList.isEmpty() && arr[linkedList.getLast()]<=arr[i]){
                        linkedList.removeLast();
                    }
                    linkedList.add(i);
                }else {
                    if (arr[i] >= arr[max]){
                        maxWindow[i-w+1]=arr[i];
                        linkedList.clear();
                        linkedList.add(i);
                    }else {
                        maxWindow[i-w+1]=arr[linkedList.getFirst()];
                        if(i-max>=(w-1)){
                            linkedList.removeFirst();
                        }
                        linkedList.peek();
                        linkedList.peekLast();
                        linkedList.removeLast();
                        linkedList.getLast();
                        while (!linkedList.isEmpty() && arr[linkedList.getLast()]<=arr[i]){
                            linkedList.removeLast();
                        }
                        linkedList.add(i);
                    }

                }
            }
        }

        System.out.println(Arrays.toString(maxWindow));

    }

    /**
     * 和上面的方法结果是一样的 只是逻辑更清晰、方式更优雅
     *
     *  需要注意 peek poll 和 get remove等方式的区别  当没有数据可操作的时候前面的返回null 后面的抛异常
     * @param arr
     * @param w
     */
    public static void getMaxWindow2(int[] arr, int w) {

        int[] rest = new int[arr.length-w+1];
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        for (int i=0;i<arr.length;i++) {
            // 这里保证了qmax中元素是有序的，前面的一定比后面的大
            while (!qmax.isEmpty() && arr[qmax.peekLast()]<=arr[i]){
                qmax.pollLast();
            }

            // 无法看到后续元素 所以这里无论大小都要先进入qmax
            qmax.add(i);

            // qmax里面的数据时有序的(前面的数据肯定比后面数据大)，每次数据只会挪动一位  所以一次最多只有一个数据需要弹出 没必要循环
            if(qmax.peekFirst() == i-w ){
                qmax.pollFirst();
            }

            // i>=w-1 之后才开始
            if (i>=w-1){
                rest[i-w+1] = arr[qmax.peekFirst()];
            }
        }
        System.out.println(Arrays.toString(rest));
    }

    public static void main(String[] args) throws Exception{

        //int[] arr= {3,5,2,7,3,6,1,5,4,3,2,1};
        //getMaxWindow(arr,3);
        //getMaxWindow2(arr,3);

        Executors.newFixedThreadPool(3);
        ScheduledExecutorService scheduledExecutorService =  Executors.newScheduledThreadPool(3);
        int i=5;
        System.out.println(System.currentTimeMillis());
        CountDownLatch downLatch = new CountDownLatch(1);
        scheduledExecutorService.schedule(()->{
            System.out.println(i);
            downLatch.countDown();
            System.out.println(System.currentTimeMillis());
            return;
        },1000, TimeUnit.MILLISECONDS);
        downLatch.await();
        scheduledExecutorService.shutdown();

    }


}
